//
// Created by Acer on 2/29 029.

#ifndef ANDROIDARCHITECT02_MAP_H
#define ANDROIDARCHITECT02_MAP_H

#include <queue>
#include <android/log.h>
using namespace std;

typedef bool rb_color; // bool类型 取别名
#define red true // 红色
#define black false //黑色


template <class K, class V>
class map {
private:
    struct TreeNode;
    int count; // 一共多少个
    TreeNode * root;

public:
    map() : root(NULL) {
        count = 0;
    }

public:
    struct iterator;

    // 获取左右儿子。
    TreeNode * left(TreeNode *pNode) {
        return pNode ? pNode->left : NULL;
    }
    TreeNode * right(TreeNode *pNode) {
        return pNode? pNode->right : NULL;
    }
    TreeNode * parent(TreeNode *pNode) {
        return pNode ? pNode->parent : NULL;
    }
    TreeNode * brother(TreeNode *pNode) {
        // 父亲的右儿子，
        return left(parent(pNode)) == pNode ? right(parent(pNode)) : left(parent(pNode));
    }
    rb_color getColor(TreeNode *pNode) {
        return pNode ? pNode->color : black; // 空节点也是黑色节点，所以返回黑。
    }
    // 染色
    void setColor(TreeNode *pNode, rb_color color) {
        if(pNode) {
            pNode->color = color;
        }
    }
    // 左旋
    TreeNode * L_Rotation(TreeNode *pNode) {
        // avl 左旋，多一个父亲对象。
        TreeNode* right = pNode->right;
        pNode->right = right->left;
        right->left = pNode;

        // 调整pNode父亲 的儿子指向
        if(pNode->parent == NULL) {
            root = right;
        } else if(pNode->parent->left == pNode ) {
            pNode->parent->left = right;
        } else {
            pNode->parent->right = right;
        }
        // 调整各大节点的父亲。
        right->parent = pNode->parent;
        if(pNode->right) {
            pNode->right->parent = pNode;
        }
        pNode->parent = right;

        return right;
    }
    // 右旋
    TreeNode * R_Rotation(TreeNode *pNode) {
        TreeNode* left = pNode->left;
        pNode->left = left->right;
        left->right = pNode;

        // 调整pNode父亲 的儿子指向
        if(pNode->parent == NULL) {
            root = left;
        } else if(pNode->parent->left == pNode ) {
            pNode->parent->left = left;
        } else {
            pNode->parent->right = left;
        }
        // 调整各大节点的父亲。
        left->parent = pNode->parent;
        if(pNode->left) {
            pNode->left->parent = pNode;
        }
        pNode->parent = left;
        return left;
    }

    // 解决双红问题
    void solveDoubleRed(TreeNode *pNode) {
        while(pNode->parent && pNode->parent->color == red) { // 情况1
            if(getColor(brother(parent(pNode))) == red) { // 情况2: 叔叔是红色
                setColor(parent(pNode), black); // 父亲染黑色
                setColor(brother(parent(pNode)), black); // 叔叔黑色
                setColor(parent(parent(pNode)), black); // 爷爷染红色

                pNode = parent(parent(pNode)); // 交给父节点处理。
            } else { // 情况3
              if(left(parent(parent(pNode)))) {
                  if(right(parent(pNode)) == pNode) { // 情况3.1
                    pNode = parent(pNode);
                    L_Rotation(pNode); // 左旋父节点
                  }
                  // 情况3.2  把我父亲这课子树上的红色节点，挪动到叔叔的那棵树上。
                  setColor(parent(pNode), black); // 父亲黑色
                  setColor(parent(parent(pNode)), red); // 爷爷红色
                  R_Rotation(parent(parent(pNode))); // 右旋爷爷
              } else {
                   if(left(parent(pNode)) == pNode) { // 情况3.1
                     pNode = parent(pNode);
                     R_Rotation(pNode); // 左旋父节点
                   }
                   // 情况3.2  把我父亲这课子树上的红色节点，挪动到叔叔的那棵树上。
                   setColor(parent(pNode), black); // 父亲黑色
                   setColor(parent(parent(pNode)), red); // 爷爷红色
                   L_Rotation(parent(parent(pNode)));
              }
            }
        }
        pNode->color = black; // 根节点黑色
    }


    iterator insert(K key, V value){ // 插入数据，返回迭代器。
        if(root == NULL) {
            root = new TreeNode(NULL,NULL,NULL, key,value, black);
            count = 1;
            return iterator(root);
        }
        TreeNode *node = root;
        TreeNode *parent = NULL;
        do {
            parent = node;
            if(key == node->key) { // key相等
                node->value = value;
                return iterator(node);
            } else { // 大，往左边走
                node = node->right;
            } else { // 往左边走
                node = node->left;
            }
        } while(node);
        TreeNode* new_node = new TreeNode(NULL,NULL,node, key,value, red);

        if(key > parent->key) {
            parent->right = new_node;
        } else {
            parent->left = new_node;
        }
        // 修正双红的现象。（）
        solveDoubleRed(new_node);
        count++; // 总数增加
        return iterator(new_node);
    }

    TreeNode* findTree(K key) {
        TreeNode* node = root;
        while(node) {
            if(key == node->key) {
                return node; // 找到了
            } else if(key > node->key) {
                node = node->right; // 往右边找
            } else { // key < node->key
                node = node->left; // 往左边找
            }
        }
        return NULL; // 没找到
    }

    // 关键代码：移除黑节点，失去了一个黑色节点。要想办法去隔壁兄弟树上拿一个红色节点过来染黑。
    // 弥补 失去的黑节点。
    void solveLostBlack(TreeNode* pNode) {
        while(pNode != root && pNode->color == black) {
            if(left(parent(pNode)) == pNode) { // 当前节点，是父节点的左节点。
                TreeNode* sib = brother(pNode); // 拿到兄弟节点
                if(getColor(sib) == red) { // 想办法把兄弟节点变成黑色。 情况1
                    setColor(sib, black); // 兄弟节点染黑，父节点染红
                    setColor(parent(pNode), red);
                    L_Rotation(parent(pNode)); // 左旋pNode
                    sib = brother(pNode);
                }
                if(getColor(left(sib)) == black && getColor(right(sib)) == black) { // 情况2
                    // 2个侄子染红
                    setColor(sib, red);
                    pNode = parent(pNode);
                } else {
                    // 情况3
                    if(getColor(right(sib)) == black) { // 远侄子黑色，把红色节点挪过来
                        setColor(sib, red);
                        setColor(left(sib), black);
                        R_Rotation(sib);
                        sib = brother(pNode); // 重置兄弟节点
                    }
                    // 情况4
                    setColor(sib, getColor(parent(pNode))); // 变成父亲的颜色
                    setColor(parent(pNode), black); // 父亲染黑
                    setColor(right(sib), black); // 右边染黑
                    L_Rotation(parent(pNode)); // 左旋

                    pNode = root; // 相当于同时两行代码： break，不要继续递归。将根节点染黑。
                }
            } else { // 当前节点，是父节点的右节点。
                 TreeNode* sib = brother(pNode); // 拿到兄弟节点
                if(getColor(sib) == red) { // 想办法把兄弟节点变成黑色。
                    setColor(sib, black); // 兄弟节点染黑，父节点染红
                    setColor(parent(pNode), red);
                    // 右旋pNode
                    R_Rotation(parent(pNode));
                    sib = brother(pNode);
                }
                if(getColor(left(sib)) == black && getColor(right(sib)) == black) {
                    // 2个侄子染红
                    setColor(sib, red);
                    pNode = parent(pNode);
                } else {
                    // 情况3，找远侄子是黑的。
                    if(getColor(left(sib)) == black) { // 远侄子黑色，把红色节点挪过来
                        setColor(sib, red);
                        setColor(right(sib), black);
                        L_Rotation(sib); // 左旋
                        sib = brother(pNode); // 重置兄弟节点
                    }
                    // 情况4
                    setColor(sib, getColor(parent(pNode))); // 兄弟节点，变成父亲的颜色
                    setColor(parent(pNode), black); // 父亲染黑
                    setColor(left(sib), black); // 右边染黑
                    R_Rotation(parent(pNode)); // 左旋

                    pNode = root;
                }
            }

        } // 结束while循环。
        // 红色，跳出循环，并设置为黑色。
        pNode->color = black;
    }

    // 移除节点
    bool remove(K key) {
        TreeNode* current = findTree(key);
        if(current == NULL) {
            return false;
        }
        if(current->left != NULL && current->right != NULL) {
            // 找后继节点
            TreeNode* successor = current->successor();
            current->key = successor->key;
            current->value = successor->value;
            current = successor;
        }
        // 要替换的节点
        TreeNode* replace = current->left ? current->left : current->right;

        // 有没有左子树，
        if(replace != NULL) { // 左子树不为空, 右子树不为空
            // 左子树的节点，放上来。 current->parent 会不会出现空的情况。
            if(current->parent == NULL) { // 根节点
                root = replace;
            }
            else if(current->parent->left == current) {
                current->parent->left = replace;
            } else {
                current->parent->right = replace;
            }
            replace->parent = current->parent;
            if(current->color == black) { // 失黑修正。
                solveLostBlack(replace);
            }
            // 删除当前节点
            delete(current);
        } else if(current->parent == NULL) {
            delete(root); // 删除根节点
            root = NULL;
        }
        else {
            // 不先移除：因为在修正的时候，需要去获取叔叔和侄子节点，来分情况判断。
            if(current->color == black) {
                solveLostBlack(replace);
            }
            // 先解决，再来移除
            if(current-> parent){
                if(current-> parent->left == current) {
                    current->parent->left = NULL;
                } else {
                    current->parent->right = NULL;
                }
            }
            delete(current);
        }

        count --;
        return true;
    }
    int size() {
        return count;
    }
    bool isEmpty(){
        return count == 0;
    }

     // 层序遍历，借助queue队列实现。
    void levelTraverse(void (*fun)(K, V, bool)) {
        if (root == NULL) {
            return;
        }
        TreeNode *node = root;
        queue<TreeNode *> nodes;
        nodes.push(node); // push 进去

        while (!nodes.empty()) { // 非空，不断地循环它
            node = nodes.front();
            fun(node->key, node->value, node->color); // 访问节点node，输出key-value
            nodes.pop(); // node弹出来

            if (node->left) { // 左边不为空，放进去
                nodes.push(node->left);
            }
            if (node->right) { // 右边不为空，放进去
                nodes.push(node->right);
            }
        }
    }
};


template <class K, class V>
struct map<>::TreeNode{
public:
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent; // 父节点
    K key;
    V value;

    rb_color color; // 节点颜色

public:
    // 构造函数，赋初始值。
    TreeNode(TreeNode* left,TreeNode* right, TreeNode* parent,K key, V value, rb_color color)
        :left(left), right(right), parent(parent), key(key), value(value), color(color) {
    }

    // 找到前驱，左边子树的最大值。
    TreeNode *precursor() {
        TreeNode *node = right;
        while(node->left) { // 不断去左边找。
            node = node->left;
        }
        return node;
    }
    // 找后继节点
    TreeNode *successor() {
        if(right != null) {
            TreeNode *successor = right;
            while(successor->left) { // 不断往左边找。
                node = successor->left;
            }
            return successor
        } else { // 不断找父节点，直到找到某个节点的左儿子，等于它。然后在网上走一层。
            TreeNode *successor = this;
            while(successor->parent && successor->parent->right == successor) {
                successor = successor->parent;
            }
            // 返回后继，在网上走一层。
            return  successor->parent;
        }
    }

};

// 定义迭代器
template <class K, class V>
struct map<K,V>::iterator {
private:
    TreeNode* node;
public:
    iterator(TreeNode* node):node(node){}

    iterator& operator--() { // 迭代器--，找前驱。返回迭代器，能再次--
         node = node->precursor();
         return *this;
    }

    iterator& operator++() { // 找后继。
        node = node->successor();
        return *this;
    }

    V operator* () {
        return node->value;
    }
};



#endif //ANDROIDARCHITECT02_MAP_H

